package leetcode

func nthUglyNumber(n int) int {
	res := make([]int, 0, n)
	n2, n3, n5 := 1, 1, 1
	i2, i3, i5 := 0, 0, 0
	for len(res) < n {
		toAppend := n2
		if n3 < toAppend {
			toAppend = n3
		}
		if n5 < toAppend {
			toAppend = n5
		}
		res = append(res, toAppend)

		if toAppend == n2 {
			n2 = 2 * res[i2]
			i2++
		}
		if toAppend == n3 {
			n3 = 3 * res[i3]
			i3++
		}
		if toAppend == n5 {
			n5 = 5 * res[i5]
			i5++
		}
	}
	return res[n-1]
}
